//Queue implementation using an array, full condition is f==r, empty is f = r-1
//Q can hold arraysize-1 elements only
//front sees inserts and rear sees removals(opposite of common usage)


#include "stdio.h"
#include "stdlib.h"


typedef int elementType;

struct queueType
{
	elementType *elemArray;
	int size, front, rear;
};

typedef struct queueType *queue;

queue createQueue(int size);
void disposeQueue(queue *pq);
int isEmpty(queue q);
void makeEmpty(queue q);
int enqueue(queue q, elementType x);
elementType dequeue(queue q);
elementType front(queue q);



queue createQueue(int  size)
{

	queue q = (queue)malloc(sizeof(struct queueType));
	if(q && size>1){  //can hold only size-1 elements, so min size = 2
		q->size = size;
		q->elemArray = (elementType*)malloc(sizeof(elementType) * size);
		if(q->elemArray){
			q->front = 1;
			q->rear = 0;
			return q;
		}

		free(q);
	}
		
		
	return NULL;
}


//Must modify calling function's queueType address holder(ptr)
void disposeQueue(queue *pq)
{
	if( pq && (*pq) && (*pq)->elemArray){
		free((*pq)->elemArray); //free the queue element array pointed to by the queueType struct at pq
		free((*pq)); //free the queueType struct
		*pq = NULL; //set the queueType struct ptr to NULL in the calling function(using address of the ptr i.e. a ptr to ptr to queueType struct)
	}
}


int isEmpty(queue q)
{
	
	int f = (q->front == 0) ? q->size-1 : q->front; //if f == 0, then f-1 is q->size - 1(front was wrapped around array end)
	if(q && q->rear == f) //r = f-1 is EMPTY condition
		return 1;
	else
		return 0;
}


void makeEmpty(queue q)
{
	if(q){	
		q->front = 1;
		q->rear = 0;
	}	
}


int enqueue(queue q, elementType x)
{
	if(q && q->rear != q->front){	//f==r is FULL condition, no element at elemArray[r]
		q->elemArray[q->front] = x;
		q->front = (q->front + 1)%(q->size);
		return 1;
	}	

	return 0;
}


//What about empty queue, how to signal it ?
elementType dequeue(queue q)
{
	elementType x;
	int r;

	if(q && !isEmpty(q)){
		r = (q->rear + 1)%(q->size);
		x = q->elemArray[r];
		q->rear = r;
		return x;
	}	

	return 0;
}


elementType front(queue q)
{
	if(q && !isEmpty(q))
		return q->elemArray[q->front];

	return 0;
}

void printQueue(queue q)
{
	int i;
	for(i=0; i<q->size; i++){
		printf("Q[%2d] = %d", i, q->elemArray[i]);

		if(i == q->front)
			printf("<-f\n");
		else if(i == q->rear)
			printf("<-r\n");
		else
			printf("\n");
	}
}


int main(int argc, char* argv[])
{
	queue q = createQueue(10);
	int i;

	for(i=0; i<12; i++){
		enqueue(q, i);
		printf("Enqueue %d\n------\n", i);
		printQueue(q);
	}

	//makeEmpty(s);

	//disposeQueue(&s);

	/*for(i=0; i<5; i++)
		printf("Top: %d\n", top(s));*/
	
	for(i=0; i<20; i++){
		if(!isEmpty(q)){
			printf("Dequeue: %d\n", dequeue(q));
			printf("------\n");
			printQueue(q);
		}
		else
			printf("Queue is empty! f=%d, r=%d \n", q->front, q->rear);
	}

			
	return 0;
}

